/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/delete-digits
   @Language: C++
   @Datetime: 16-02-09 05:47
   */

// Method 1, Erase element k times, Time O(n*k)
class Solution {
public:
	/**
	 * @param A: A positive integer which has N digits, A is a string.
	 * @param k: Remove k digits.
	 * @return: A string
	 */
	string DeleteDigits(string A, int k) {
		// wirte your code here
		if (A.length()<=k) return "0";
		for(int i=0; i<A.length() && k;){
			if(i+1<A.length() && A[i]>A[i+1]){
				A.erase(A.begin()+i);
				i = max(0,i-1);
				--k;
			}
			else ++i;
		}
		A.erase(A.length()-k);  // last k nums are in ascending order
		return A.substr(A.find_first_not_of('0'));  // trim begin 0
	}
};

// Method 2, Add mini-element to new string s, Time O(n+k)
class Solution {
public:
	/**
	 * @param A: A positive integer which has N digits, A is a string.
	 * @param k: Remove k digits.
	 * @return: A string
	 */
	string DeleteDigits(string &A, int k) {
		// wirte your code here
		if (A.size()<=k) return "0";
		string s;
		for(int i=0; i<A.size(); s.push_back(A[i++]))
			for(; s.size() && k && s.back()>A[i]; --k)
				s.pop_back();
		s.erase(s.size()-k);	// last k eles are in ascending order
		return s.substr(s.find_first_not_of('0'));	// trim begin 0
	}
};
